1. Field of the Invention
The present invention relates to an error correction encoding method and apparatus, and an error correction decoding method and apparatus. More particularly, it relates to a method and apparatus for encoding turbo codes as well as a method and apparatus for decoding turbo codes.
2. Description of the Related Art
A known turbo encoding method will be described below. FIG. 10 is a flow chart illustrating the known turbo encoding method using a turbo encoder which will be described later. In FIG. 10, ST71 designates a processing step for determining the block length N of an interleaver at the start of transmission. ST72 designates a processing step for preparing an interleaver pattern of the block length N. ST73 designates a processing step for initializing the value of each register 65 of a first convolutional encoder and the value of each register 66 of a second convolutional encoder. ST74 designates a processing step for buffering an information bit sequence u for one block. ST75 designates a processing step for performing turbo encoding with a turbo encoder 61, and outputting parity bit sequences pa and pb. ST76 designates a processing step for calculating tail bits t used to return the registers 65 and 66 to their initial values. ST77 designates a processing step for determining whether a frame being now processed is the last (final) one, and switching the processing operation.
FIG. 11 illustrates the configuration of the turbo encoder used at the sending side for implementing the above-mentioned turbo encoding method. In FIG. 11, the turbo encoder, generally designated at reference numeral 61, includes a first recursive systematic convolutional encoder 62 (hereinafter, referred to simply as a first convolutional encoder) for convolutionally encoding an information bit sequence u to output a parity bit sequence pa, an interleaver 63, a second recursive systematic convolutional encoder 64 (hereinafter, referred to simply as a second convolutional encoder) for convolutionally encoding the information bit sequence u, which has been permuted by the interleaver 63, thereby to output a parity bit sequence pb, the registers 65 of the first convolutional encoder 62, and the registers 66 of the second convolutional encoder 64.
FIG. 12 is the configuration of the information bit sequence and the parity bit sequences which have been encoded by the known encoding method and each merged into one frame. In FIG. 12, 51 designates the information bit sequence u input to the turbo encoder 61. 52 designates the parity bit sequence pa output from the first convolutional encoder 62. 53 designates the parity bit sequence pb output from the second convolutional encoder 64. 54 designates tail bits ta, u for returning the registers in the first convolutional encoder 62 to their initial values. 56 designates tail bits ta, p for returning the registers in the first convolutional encoder 62 to their initial values. 55 designates tail bits tb, u for returning the registers in the second convolutional encoder 64 to their initial values. 57 designates tail bits tb, p for returning the registers in the second convolutional encoder 64 to their initial values.
FIG. 13 illustrates the configuration of an iterative decoder used at the receiving side. In FIG. 13, a first soft-input and soft-output decoder 81 (hereinafter, referred to simply as a first decoder) is input with reception sequences x, ya, za, u, za, p and priori information (logarithm of priori information ratio) La(u), and calculates log-likelihood ratio L(u) therefrom. A second soft-input and soft-output decoder 82 (hereinafter, referred to simply as a second decoder) is input with reception sequences x, yb, zb, u, zb, p, and priori information La(u), and calculates log-likelihood ratio L(u). The iterative decoder further includes interleavers 83 and 84, a deinterleaver 85, a first adder 86, a second adder 87, a determiner 88 for calculating an estimate value of a transmitted information bit sequence from the log-likelihood ratio L(u) output from the second decoder 82, and a switch 89 for switching the priori information La(u), which is input to the first decoder 81, to an initial value 0 or a value output from the second adder 87.
FIG. 14 is a flow chart showing an MAP (maximum a posteriori) decoding method, which is one technique of a calculation means of the soft-input and soft-output decoder (i.e., the first decoder 81 and the second decoder 82) used at the receiving side. In FIG. 14, an initial value α(Sj,0) of a forward path metric α(Sj,k), k=0, 1, 2, . . . , N (k represents a point in time) is set in step ST101. The time point k is initialized to 1 in step ST102. Branch metrics γi,k is calculated in step ST103. A forward path metric α(Sj,k) is calculated in step ST104. The forward path metric α(Sj,k) thus calculated is stored in a memory in step ST105. It is determined in step ST106 whether the time point k has become N or more. The time point k is incremented by 1 in step ST107. An initial value β(Sj,n+T) of a backward path metric β(Sj,k), k=1, 2, . . . , N+T (k designates time points) is set in step ST108. The time point k is initialized to N+T−1 in step ST109. The branch metric γi,k is calculated in step ST110. The backward path metric β(Sj,k) is calculated in step ST111. Logarithmic likelihood ratio L(uk) is calculated in step ST112. An extrinsic information Le(uk) is calculated in step ST113. It is determined in step ST114 whether the time point k has become 1 or less. The time point k is decremented by 1 in step ST115.
Next, the operation of the known encoding method will be described concretely. An information bit sequence u: u1, u2, . . . , uN is successively input to the turbo encoder 61 shown in FIG. 11 in the order of time points 1, 2, . . . , N, respectively. That is, the first recursive systematic convolutional encoder 62 of the turbo encoder 61 encodes the information bit sequence u input thereto, and outputs a parity bit sequence pa: pa, 1, pa, 2, . . . , pa, N.
In order to return the registers of the first convolutional encoder 62 to their initial values after the last or final information bit uN is input to the first convolutional encoder 62 at time point N, the tail bits ta, u and the tail bits ta, p are calculated (here, the lengths of tail bits ta, u and ta, p are assumed to be T, respectively.). The tail bits can be uniquely calculated according to the values of the registers after the last information bit uN has been input. The registers are returned to their initial values when the tail bits ta, u are input to the first convolutional encoder 62. The first convolutional encoder 62 outputs the tail bits ta, p as parity bits.
The second convolutional encoder 64 of the turbo encoder 61 successively encodes sequences of information bits u which have been permuted by the interleaver 63 and input thereto, and outputs the parity bit sequence pb: pb, 1, pb, 2, . . . , pb, N.
After the last information bit uN is input at time point N, the tail bits tb, u and the tail bits tb, p for returning the registers of the second convolutional encoder 64 to their initial values are calculated (the lengths of tb, u and tb, p are assumed to be T, respectively). The tail bits can be uniquely calculated according to the values of the registers after the last information bit uN has been input. When the tail bits tb, u are input to the second convolutional encoder 64, the registers therein are returned to their initial values, and the second convolutional encoder 64 outputs the tail bits tb, p as parity bits.
After the encoding processing as described above has been done, the information bit sequence u, the parity bit sequences pa, pb and the tail bits ta, u, ta, p, tb, u, tb, p are transmitted, as shown in FIG. 12.
In the turbo encoder 61, the information bit sequence u input to the second convolutional encoder 64 is required to be permuted by the interleaver 63. Therefore, it is necessary to divide the information bit sequence u into units of blocks of N in length. The interleaver 63 permutes the information bit sequences u1, u2, . . . , uN thus divided into the block units, respectively, of N in length. The information bit sequences, the parity bit sequences and the tail bit sequences finally encoded are transmitted in frames, as shown in FIG. 12.
Next, reference will be made to the processing procedure according to the turbo encoding from the start to the end of transmission while referring to FIG. 10. First of all, the block length N in the interleaver 63 is decided in step ST71 as shown in FIG. 10. Then, an interleaver pattern for the block length N is prepared in step ST72. The registers D of the convolutional encoders are initialized in step ST73. After the information bit sequence u to be transmitted has been buffered in step ST74, the turbo encoding processing is carried out to output parity bit sequences pa, pb in step ST75. Tail bits t are output in step ST76. In step ST77, it is determined whether the transmission frame being now processed is the last one. When the frame being now processed is not the last one, a return is performed to step ST73 where the registers D of the convolutional encoders are initialized, and the turbo encoding is continued. When the frame being now processed is the last one, the transmission processing is terminated.
At the receiving side, there are received a reception sequence x which is the information bit sequence u being transmitted and added with noise on the transmission path or channel, reception sequences ya and yb which are the parity bit sequences pa and pb being transmitted and added with noise on communication channels, and reception sequences Za, u, za, p, zb, u, zb, p which are the tail bits being transmitted and added with noise on communication channels. Because the interleaver is used for encoding, decoding of turbo symbols cannot be started until all the reception sequences of 3N+4T in length are received. After the reception has been completed, the reception sequences are input to the iterative decoder where they are subjected to iterative decoding.
Here, concrete reference will be made to the operation of the iterative decoder shown in FIG. 13. At the receiving side, there are received the reception sequences x: x1, x2, . . . , xN which are the information bit sequence u being transmitted and added with noise on communication channels, a reception sequence ya: ya, 1, ya, 2. . . , Ya, N which is the parity bit sequence pa being transmitted and added with noise on communication channels, the reception sequence yb: yb, 1, yb, 2, . . . , yb, N which is the parity bit sequence pb being transmitted and added with noise on communication channels, and reception sequences za, u, za, p, zb, u, zb, p which are the tail bits ta, u, ta, p, tb , u, tb, pbeing transmitted and added with noise on communication channels.
First of all, the reception sequences x, ya, za, u Za, p are input to the first decoder 81. Moreover, the switch 89 is thrown to a side A only at a decoding start time point. An initial value 0 is input as the priori information: La(uk), k=1, 2, . . . , N. The first decoder 81 performs the soft-input and soft-output decoding from these input values to calculate the logarithmic likelihood ratio: L(uk), k=1, 2, . . . , N corresponding to the information bits uk (here, k designates time points). At this time, the logarithmic likelihood ratio: L(uk) can be represented by the following expression (1).                                                                                           L                  ⁡                                      (                                          u                      k                                        )                                                  =                                                      L                    ⁢                                                                                   ⁢                                          c                      ·                                              x                        k                                                                              +                                      L                    ⁢                                                                                   ⁢                                          a                      ⁡                                              (                                                  u                          k                                                )                                                                              +                                      L                    ⁢                                                                                   ⁢                                          e                      ⁡                                              (                                                  u                          k                                                )                                                                                                                                                                    =                                  ln                  ⁢                                                                           ⁢                                                            Pr                      ⁡                                              (                                                                              u                            k                            ′                                                    =                                                      1                            |                                                          {                              Y                              }                                                                                                      )                                                                                    P                      ⁢                                                                                           ⁢                                              r                        ⁡                                                  (                                                                                    u                              k                              ′                                                        =                                                          0                              |                                                              {                                Y                                }                                                                                                              )                                                                                                                                                                                     (        1        )            where Le(uk) represents extrinsic information; La(uk) represents the value which is calculated with one-preceding extrinsic information being taken as the priori information; Pr(u′k=1|{Y}) represents a probability that the estimated information bits: u′k calculated with the whole sequence {Y} of the reception signal having been received are 1; Pr(u′k=0|{Y}) represents a probability that the estimated information bits: u′k calculated with the whole sequence {Y} of the reception signal having been received are 0. That is, the probability of the estimated information bits u′k being 1 with respect to the probability of the estimated information bits u′k being 0 is calculated according to expression (1) above. Also, note that Lc·xk represents a communication channel value.
Subsequently, the first adder 86 calculates the extrinsic information for the second decoder 82 from the logarithmic likelihood ratio which are the result of above-mentioned calculations. The extrinsic information: Le(uk), k=1, 2, . . . , N can be represented by the following expression (2) based on expression (1) above.Le(uk)=L(uk)−Lc·xk−La(uk)  (2)
Here, note that La(uk) is equal to 0 in the first decoding because the priori information has not been calculated.
Then, the interleavers 83 and 84 permute the reception sequence x and the sequence of extrinsic information Le(uk) so as to match the time point of the reception sequence Yb. The second decoder 82 calculates the logarithmic likelihood ratio: L(uk) based on the reception sequences x, yb, zu, b, zb, p and the extrinsic information: Le(uk) previously calculated, as in the first decoder 81. Thereafter, the second adder 87 calculates the extrinsic information: Le(uk) by using expression (2) above, as in the first adder 86. At this time, the extrinsic information permuted by the deinterleaver 85 is fed back to the first decoder 81 as the priori information: La(uk).
Finally, the iterative decoder calculates the logarithmic likelihood ratio with higher accuracy by repeatedly executing the above-mentioned processing over a prescribed number of times. The determiner 88 makes a determination based on the logarithmic likelihood ratio thus calculated thereby to estimate the original information bit sequence. Stated concretely, if the logarithmic likelihood ratio L(uk) is greater than zero (L(uk)>0), it is determined that the estimated information bits: u′k is 1. If L(uk)≦0, the estimated information bits: u′k is determined to be 0.
Here, the operation of the soft-input and soft-output decoder (the first decoder 81 and the second decoder 82) will be described concretely. The information bit sequence, the parity bit sequence and the tail bits generated by the convolutional encoder together form a diagram called a trellis consisting of branches (indicative of transitions of states) and nodes (indicative of the states of the registers in the convolutional encoders). An MAP decoding shown in FIG. 14 searches for this trellis diagram based on a reception sequence, and estimates a transmitted information bit sequence.
Here, the state of each register is defined as Sj, k (j is the decimal notation of the value of each register, and k represents the time point.). In addition, the labels of branches, which are passed when the information bit uk is input and the parity bit pk is output, are defined as ik=(uk, pk). First of all, a search is run through the trellis in a forward direction from time point k=1. Here, note that the a posteriori probability of the transmission information bit sequence having passed the state Sj, k upon receipt of a reception sequence from time point 1 to time point k is defined as the forward path metric: α(Sj, k). In step ST101, the initial value α(Sj, 0) of the forward path metric α(Sj, k) is set. This is set as shown in the following expression (3) according to the MAP decoding.                               α          ⁡                      (                          S                              j                ,                0                                      )                          =                  {                                                                      1                  ,                                                                                                  if                    ⁢                                                                                   ⁢                    j                                    =                  0                                                                                                      0                  ,                                                            otherwise                                                                        (        3        )            
In step ST102, the time point k is set to 1. In step ST103, the concatenated probability: (branch metric γi, k) of a branch with a branch label ik being passed through is calculated. The calculation of the branch metric γi, k varies depending on the state of communication channels and the modulation method. For instance, let us assume the case where BPSK modulation is performed in the white Gaussian noise communication channel. Assuming that a variance of noise is σ2, and the amplitude values of the reception signals of information bits and parity bits are xk and yk, respectively, the branch metric γi, k is calculated as shown in the following expression (4).                               γ                      i            ,            k                          =                  exp          ⁢                      {                                                                                (                                                                  2                        ⁢                                                  u                          k                                                                    -                      1                                        )                                    ·                                      x                    k                                                                    σ                  2                                            +                                                                    (                                                                  2                        ⁢                                                  p                          k                                                                    -                      1                                        )                                    ·                                      y                    k                                                                    σ                  2                                            +                                                                                          (                                                                        2                          ⁢                                                      u                            k                                                                          -                        1                                            )                                        ·                    L                                    ⁢                                                                           ⁢                                      a                    ⁡                                          (                                              u                        k                                            )                                                                      2                                      }                                              (        4        )            where La(uk) is the priori information of the last but one extrinsic information.
In step ST104, the forward path metric α(Sj, k), is calculated according to the following expressions (5) and (6).                               α          ⁡                      (                          S                              j                ,                k                                      )                          =                              h                          α              ,              k                                ⁢                                    ∑              i                        ⁢                                          α                ⁡                                  (                                      S                                                                  j                        ′                                            ,                                              k                        -                        1                                                                              )                                            ·                              γ                                  i                  ,                  k                                                                                        (        5        )                                          h                      α            ,            k                          =                  1                                    ∑              j                        ⁢                          α              ⁡                              (                                  S                                      j                    ,                    k                                                  )                                                                        (        6        )            
where the summation in expression (5) above is calculated only for the branches which enter the state Sj, k. In step ST106, the forward path metric α(Sj, k) thus calculated is stored in a memory. In step ST107, a comparison is made as to whether the time point k is equal to or larger than the block length N. When the time point k is smaller than the block length N, the time point k is incremented by 1, and step ST103 is carried out, whereas when the time point k is equal to or larger than the block length N, the forward path metric operation is ended.
Thereafter, a search is made for the trellis from time point k=N+T in a backward direction. Here, note that the a posteriori probability of the transmission information bit sequence having passed the state Sj, k upon receipt of the reception sequence from time point k+1 to time point N+T is defined as the backward path metric: β(Sj, k). In step ST108, the initial value β(Sj, N+T) of the backward path metric β(Sj, k) is set. This is set as shown in the following expression (7) according to the MAP decoding.                               β          ⁡                      (                          S                              j                ,                                  N                  +                  T                                                      )                          =                  {                                                                      1                  ,                                                                                                  if                    ⁢                                                                                   ⁢                    j                                    =                  0                                                                                                      0                  ,                                                                              o                  ⁢                                                                           ⁢                  t                  ⁢                                                                           ⁢                  h                  ⁢                                                                           ⁢                  e                  ⁢                                                                           ⁢                  r                  ⁢                                                                           ⁢                  w                  ⁢                                                                           ⁢                  i                  ⁢                                                                           ⁢                  s                  ⁢                                                                           ⁢                  e                                                                                        (        7        )            
The reason for the initial value β(Sj, N+T) of the backward path metric β(Sj, k) being able to be set as shown in expression (7) above is that the trellis is converged to a node (S0, N+T) of the initial state owing to the addition of the tail bits tu, tp. In step ST109, the time point k is set to N+T−1.
In ST110, the concatenated probability: (branch metric γi, K+1) of the branch with the branch label ik being passed through is calculated according to the above-mentioned expression (4). In step ST111, the backward path metric β(Sj, k) is calculated according to the following expressions (8) and (9).                               β          ⁡                      (                          S                              j                ,                k                                      )                          =                              h                          β              ,              k                                ⁢                                    ∑              i                        ⁢                                          β                ⁡                                  (                                      S                                                                  j                        ′                                            ,                                              k                        +                        1                                                                              )                                            ·                              γ                                  i                  ,                                      k                    +                    1                                                                                                          (        8        )                                          h                      β            ,            k                          =                  1                                    ∑              j                        ⁢                          β              ⁡                              (                                  S                                      j                    ,                    k                                                  )                                                                        (        9        )            
However, the summation in the expression (8) is calculated only for the branches which extend from the state Sj, k.
In step ST111, for time points k=N+T, N+T−1, . . . , N+1 corresponding to the tail bits, xk and yk in the expressions for calculating the branch metrics γi, k are replaced by za, u, k (or zb, u, k and za, p, k (or zb, p, k). In addition, the priori information La(uk) is assumed to be 0.
In step ST112, the logarithmic likelihood ratio L(uk) is calculated according to the following expressions (10)-(12).                               L          ⁡                      (                          u              k                        )                          =                  ln          ⁢                                           ⁢                                                    ∑                                                      i                    k                                    ,                                                            u                      k                                        =                    1                                                              ⁢                                                ∑                                      S                                          j                      ,                      k                                                                      ⁢                                  σ                  ⁡                                      (                                                                  S                                                  j                          ,                          k                                                                    ,                                              i                        k                                                              )                                                                                                      ∑                                                      i                    k                                    ,                                                            u                      k                                        =                    0                                                              ⁢                                                ∑                                      S                                          j                      ,                      k                                                                      ⁢                                  σ                  ⁡                                      (                                                                  S                                                  j                          ,                          k                                                                    ,                                              i                        k                                                              )                                                                                                          (        10        )                                          σ          ⁡                      (                                          S                                  j                  ,                  k                                            ,                              i                k                                      )                          =                              h                          σ              ,              k                                ·                      α            ⁡                          (                              S                                  j                  ,                                      k                    -                    1                                                              )                                ·                      γ                          i              ,              k                                ·                      β            ⁡                          (                              S                                                      j                    ′                                    ,                  k                                            )                                                          (        11        )                                          h                      σ            ,            k                          =                  1                                    ∑                              i                k                                      ⁢                                          ∑                j                            ⁢                              σ                ⁡                                  (                                                            S                                              j                        ,                        k                                                              ,                                          i                      k                                                        )                                                                                        (        12        )            
In step ST113, the extrinsic information Le(uk) is calculated by the aforementioned expression (2). Here, communication channel value: Lc·xk in the current condition is calculated as shown by the following expression (13).                               L          ⁢                                           ⁢                      c            ·                          x              k                                      =                              2            ·                          (                                                2                  ⁢                                      u                    k                                                  -                1                            )                        ·                          x              x                                            σ            2                                              (        13        )            
Note that the calculations according to the expression (2) are carried out by the adders 86 and 87. In step ST114, a comparison is made as to whether the time point k is equal to or less than 2. When the time point k is larger than 2, k is decremented by 1 and the processing in step ST110 is carried out. When the time point k is equal to or less than 2, the backward path metric operation is ended, and the soft-input and soft-output decoding processing is also ended.
Note that for time points k=N+T, N+T−1, . . . , N+1 corresponding to the tail bits, the arithmetic operations in step ST112 and step ST113 are not carried out.
The known encoding method as constructed above has the following problems. That is, it is necessary to concurrently transmit the tail bits for initializing the registers of the encoders besides the information bit sequence and the parity bit sequences originally intended to be transmitted. The tail bits themselves are redundant, accordingly reducing the transmission efficiency. Moreover, it is necessary to secure areas for the tail bits in the transmission frames, thus giving limitations to the configuration of the transmission frames.